package com.sicheng.lc.周赛.分类.二分or排序;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/6/23 11:40
 */
public class 每个小孩最多能分到多少糖果 {
    //https://leetcode.cn/problems/maximum-candies-allocated-to-k-children/
    public int maximumCandies(int[] candies, long k) {
        long sum = 0;
        for (int candy : candies) {
            sum += candy;
        }

        if (k > sum) {
            return 0;
        }
        if (k == sum)
            return 1;
        long l = 1;
        long r = sum;
        long res = 0;
        while (l <= r) {
            long mid = l + r >> 1;
            if (distributed(candies, k, mid)) {
                res = mid;
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return (int) res;
    }

    private boolean distributed(int[] candies, long k, long m) {
        for (int candy : candies) {
            if (candy >= m) {
                k -= candy / m;
            }
            if (k <= 0)
                return true;
        }
        return false;
    }

    public static void main(String[] args) {
        每个小孩最多能分到多少糖果 solution = new 每个小孩最多能分到多少糖果();
        int[] candies = {1000};
        int k = 1;
        System.out.println(solution.maximumCandies(candies, k));
    }
}
